建议先做 CF439E。
n=1∑yi1=1∑yi2=1∑y...in=1∑y[∑ai=y][gcdai=x]
n=1∑yi1=1∑xyi2=1∑xy...in=1∑xy[∑ai=xy][gcdai=1]
n=1∑yd∣xy∑μ(d)i1=1∑xdyi2=1∑xdy...if=1∑xdy[∑ai=xdy]
后面枚举 i 的过程可以看作将 xdy 个相同的球放进 n 个不同的盒子,且不能有空盒的方案数,利用插板法可得: (n−1xdy−1)
那么原式即为:
n=1∑yd∣xy∑μ(d)(n−1xdy−1)
d∣xy∑μ(d)n=1∑y(n−1xdy−1)
d∣xy∑μ(d)n=1∑xdy(n−1xdy−1)
d∣xy∑μ(d)n=1∑xdy(n−1xdy−1)
d∣xy∑μ(d)2xdy−1
#include <cstdio>
const int MAXN = 1e5 , Mod = 1e9 + 7;
int Quick_pow( int x , int po ) { int p = 1; for( ; po ; po >>= 1 , x = 1ll * x * x % Mod ) if( po & 1 ) p = 1ll * p * x % Mod; return p; }
int Inv( int x ) { return Quick_pow( x , Mod - 2 ); }
int mu( int n ) {
int Ans = 1;
for( int i = 2 ; i * i <= n ; i ++ )
if( n % i == 0 ) {
int p = 0; for( ; n % i == 0 ; n /= i ) p ++;
if( p > 1 ) return 0;
Ans *= -1;
}
if( n > 1 ) Ans *= -1;
return Ans;
}
int x , y;
int main( ) {
scanf("%d %d",&x,&y);
if( y % x != 0 || y < x ) return printf("0\n") & 0;
int Ans = 0;
for( int d = 1 ; d * d <= y / x ; d ++ )
if( y / x % d == 0 ) {
Ans = ( Ans + mu( d ) * Quick_pow( 2 , y / x / d - 1 ) % Mod ) % Mod;
if( d * d != y / x )
Ans = ( Ans + mu( y / x / d ) * Quick_pow( 2 , d - 1 ) % Mod ) % Mod;
}
printf("%d\n", ( Ans + Mod ) % Mod );
return 0;
}